oo
o
O
(N
m
c3
ON A THEOREM OF SHKREDOV
TOM SANDERS
Abstract. We show that if A is a finite subset of an abelian group with ad-
ditive energy at least c\A\ 3 then there is a set C C A with \C\ = (^(c -1 log |j4|)
such that |AnSpan(£)| = £l(c 1 / 2 \A\).
1. Introduction and notation
.^ , We shall prove the following theorem which is a slight strengthening of |Shk07|
r \ ' Theorem 1.5].
c"| Theorem 1.1. Suppose that G is an abelian group and A c G is a finite set with
\\1a * MIp(g) ^ C \ A \ 3 - Then there is a set £ C A with \C\ = O^ 1 log \A\) such
thaR \A n Span(£)| = Sl(cV 2 \A\).
It is immediate from the Cauchy-Schwarz inequality that if |.<4 + .A| ^ K\A\ then
I! 1a * 1a|!£2( G -) ^ l^4| 3 /^ whence the conclusion of the above result applies to A.
This was noted by Shkredov in [Shk07l Corollary 3.2], however, something slightly
stronger is also trueo
Theorem 1.2. Suppose that G is an abelian group and A C G is a finite set with
\A + A\ < K\A\. Then there is a set C C A with \C\ = 0(K log |A|) such that
4cS P an(£).
Before we begin with our proofs it will be useful to recall some well-known tools;
Rudin |Rud90j is the classic reference for these.
A subset C of an abelian group G is said to be dissociated if
/\ • 2_. a x- x = Og and a e {—1, 0, 1} £ implies that a = 0.
Algebraically, dissociativity is particularly useful in view of the following easy
lemma.
Lemma 1.3. Suppose that G is an abelian group and A C G is finite. If C C A is
a maximal dissociated subset of A then A C Span(£).
Analytically, dissociativity can be handled very effectively using the Fourier
transform which we take a moment to introduce.
Suppose that G is a (discrete) abelian group. We write G for the dual group, that
is the compact abelian group of homomorphisms from G to S 1 := {z € C : \z\ = 1}
Recall that Span(£) is the set of all sums 5Za;G£ (T».x where a £ {—1, 0, 1} £
Since writing these notes it has
independently proved Theorem 11.21
Since writing these notes it has come to the author's attention |Shk| that Shkredov has also
TOM SANDERS
endowed with the Haar probability measure /ig, and define the Fourier transform
of a function / 6 £ 1 (G) to be
/:G^C; 7-^/(^)7(3
xEG
The following result is a key tool in harmonic analysis.
Proposition 1.4 (Rudin's inequality). Suppose that G is an abelian group and
C C G is a dissociated set. Then, for each p € [2, 00) we have
ll/IU^e) = 0(Vp\\f\\mc)) for all f G £ 2 (£).
2. The proof of Theorem II. II
Our proof of Theorem 1 1.1 1 is guided by Shkredov [Shk07] although we are able to
make some simplifications by using some standard facts about the L p (/zg)-norms.
Wc require the following lemma which is contained in the paper Bou90] of
Bourgain.
Lemma 2.1. Suppose that G is a abelian group, A c G is finite, I is a positive
integer and p ^ 2. Then there is a set A' C A such that all dissociated subsets of
A' have size at most I and
\\lA-lA>\\L*Qi )=0(y/ P /l\A\).
Proof. We define sets A D A x D ■ ■ ■ D A s and £ , C\, . . . ,£ s iteratively starting
with A Q := A. Suppose that we have defined Ai.
(i) If there is no dissociated subset of Ai with size I then terminate the itera-
tion;
(ii) if there is a dissociated subset of A4 with size I then let Li be any such set
and put Ai + i — Ai\ d.
The algorithm terminates at some stage s with s ^ \A\/l since |Aj+i| = \Ai\ — I.
Write A' := A s which consequently has no dissociated subset of size greater than I.
Since A is the disjoint union of the sets Co, ■ ■ ■ , C s -i and A! we have
s-1 s-1
II 1,4- 1a'IUj>0* 8 ) = II^Z 1c 'II Lp ^g) ^ zJll^H^Oe)'
Now each summand is 0(y / p||l£ i ||^2(£.)) = 0(\/pl), by Rudin's inequality, whence
llO - G\\lHp s ) = 0{s^pl) = 0{^pJl\A\),
in view of the upper bound on s. □
Proof of Theorem \l.l\ Write p := 2 + log |.<4| and let I be an integer with I =
<3(p C -(p-2)/p|^|2/p) _ ( c -i log ^ such that when we apply LemmaHUto A we
get a set A' d A for which
(2.1) ||U - QlliP^) < c<*-*>/*>\A\<*-Wv/2.
Let £ be a maximal dissociated subset of A'. We have \C\ ^ I = 0(cr l log \A\) by
the choice of I, and A' C Span(£) by Lemma [TT3l whence \AC\ Span(£)| ^ \A'\ and
the result will follow from a lower bound on \A'\.
By the log-convexity of the L p {^,~) norms we have
\\U\W e ) < ll^lli 2 C/ (P " } |l^ll-(t) 2) - W^'^llQ^.
ON A THEOREM OF SHKREDOV 3
where the equality is by Parseval's theorem. However, we are given that the left
hand side is at least c|j4| 3 , whence we get the lower bound
(2.2) \\u\\L P{ » s )>c {p ~ 2)/2p \A\ (p - 1)/p .
On the other hand using Holder's inequality we have the upper bound
llGll^a) < llGll^jllGllfegg < \Ar~ 1)/p ,
where the second inequality is by Parseval's theorem and the Hausdorff- Young
inequality applied to the L 2 -norm and L°°-norm respectively.
By the triangle inequality, this and (|2.2|) give
IIU - G'hnno) > c^-^/^iai^- 1 )/" - ia'i^-v/p.
Using the upper bound on the left hand side from (J2.1D it follows that
\A'\ > c (p-2)/2(p-D 2 -p/(p-i)|A| > c l ' 2 \A\/A,
as required. □
3. The proof of Theorem 11.21
The proof is essentially Theorem 6.10 of Lopez and Ross [LR75] coupled with
Lemma 11.31
Proof of Theorem[FE Write / := \ A+A * 1_ A , Then
Li(Mg) = / IWa(7)1-a(7)MMgW
: ( / |l, + i(-l| 2 dMe(7)) f/|C4( 7 )| 2 d/ie(7) V '
= y/\A + A\\-A\^VK\A\,
by the Cauchy-Schwarz inequality, Parseval's theorem and the doubling condition
\A + A\ s$ K\A\, Furthermore \\f\\i^ {G ) < \A\ and ||/||/i( G ) = \A\\A + A\ and so
ll/llWg) = WfWrw < ||/IU»(G).||/IUx(G) < 14V + 4 < tf|A| 3 ,
by Parseval's theorem, Holder's inequality and the doubling condition. Whence, by
log-convexity of the L p (//g) norms, we have
\\f\\ LP ' ( , e) ^VK\A\^+^ior & l\p'e[l,2}.
Suppose that £ is a maximal dissociated subset of A and (p,p') is a conjugate
pair of exponents with p' e (1,2]. Then, by Rudin's inequality we have
\\f\\l>(C) = (f 1 C,f}v>(M S ) < \\f 1 c\\LP( Ms )\\f\\ L p'^ e )
= =0(Vp.\\f\\mc)\\f\\ LP ' { , 8) )-
The construction of / ensures that for any aei, f(a) — Ia+a * 1— a(o) #* \A\ so,
canceling ||/||^2( £ ) above we get
Vn\W < ii/ii^(£) = o(vpii/ii^ ( ^)) = o(v^i^i (p,+1)/2 )-
Putting p = 2 + log | A| and some rearrangement tells us that |£| = 0(if log |^4|).
Since £ was maximal Lemma 11.31 then yields the result. □
TOM SANDERS
References
[Bou90] J. Bourgain. On arithmetic progressions in sums of sets of integers. In A tribute to Paul
Erdos, pages 105-109. Cambridge Univ. Press, Cambridge, 1990.
[LR75] J. M. Lopez and K. A. Ross. Sidon sets. Marcel Dekker Inc., New York, 1975. Lecture
Notes in Pure and Applied Mathematics, Vol. 13.
[Rud90] W. Rudin. Fourier analysis on groups. Wiley Classics Library. John Wiley & Sons Inc.,
New York, 1990. Reprint of the 1962 original, A Wiley-Interscicnce Publication.
[Shk] I. D. Shkrcov. Personal communication.
[Shk07] I. D. Shkrcdov. On sets with small doubling. Preprint, 2007.
Department of Pure Mathematics and Mathematical Statistics, University of Cam-
bridge, WlLBERFORCE ROAD, CAMBRIDGE CB3 0WA, ENGLAND
E-mail address: t .sandersadpmms.cam.ac.uk